翻訳と辞書 Words near each other ・ Post Tower ・ Post town ・ Post Town, Minnesota ・ Post Township, Allamakee County, Iowa ・ Post Track ・ Post Traumatic Slave Syndrome ・ Post Tropical ・ Post turtle ・ Post University ・ Post van ・ Post viral cerebellar ataxia ・ Post void ・ Post Wheeler ・ Post's inversion formula ・ Post's lattice ・ Post's theorem ・ Post, Iran ・ Post, Oregon ・ Post, Texas ・ Post- och Inrikes Tidningar ・ Post-1913 Dioceses of the Church of the East ・ Post-2008 Irish banking crisis ・ Post-2008 Irish economic downturn ・ Post-2015 Development Agenda ・ Post-80s ・ Post-9/11 ・ Post-9/11 Veterans Educational Assistance Act of 2008 ・ Post-90s ・ Post-ablation tubal sterilization ・ Post-acute-withdrawal syndrome Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Post's theorem ： ウィキペディア英語版 Post's theorem In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees. == Background == The statement of Post's theorem uses several concepts relating to definability and recursion theory. This section gives a brief overview of these concepts, which are covered in depth in their respective articles. The arithmetical hierarchy classifies certain sets of natural numbers that are definable in the language of Peano arithmetic. A formula is said to be $\backslash Sigma^\_m$ if it is an existential statement in prenex normal form (all quantifiers at the front) with $m$ alternations between existential and universal quantifiers applied to a quantifier free formula. Formally a formula $\backslash phi(s)$ in the language of Peano arithmetic is a $\backslash Sigma^\_m$ formula if it is of the form :$\backslash exists\; n\_1\; \backslash forall\; n\_2\; \backslash exists\; n\_3\; \backslash forall\; n\_4\; \backslash cdots\; Q\; n\_m\; \backslash rho(n\_1,\backslash ldots,n\_m,x\_1,\backslash ldots,x\_k),$ where ρ is a quantifier free formula and ''Q'' is $\backslash forall$ if ''m'' is even and $\backslash exists$ if ''m'' is odd. Note that any formula of the form :$\backslash left(\backslash exists\; n^1\_1\backslash exists\; n^1\_2\backslash cdots\backslash exists\; n^1\_\backslash right)\backslash left(\backslash forall\; n^2\_1\; \backslash cdots\; \backslash forall\; n^2\_\backslash right)\backslash left(\backslash exists\; n^3\_1\backslash cdots\backslash right)\backslash cdots\backslash left(Q\_1\; n^m\_1\; \backslash cdots\; \backslash right)\backslash rho(n^1\_1,\backslash ldots\; n^m\_,x\_1,\backslash ldots,x\_k)$ where $\backslash rho$ contains only bounded quantifiers is provably equivalent to a formula of the above form from the axioms of Peano arithmetic. Thus it isn't uncommon to see $\backslash Sigma^\_m$ formulas defined in this alternative and technically nonequivalent manner since in practice the distinction is rarely important. A set of natural numbers ''A'' is said to be $\backslash Sigma^0\_m$ if it is definable by a $\backslash Sigma^0\_m$ formula, that is, if there is a $\backslash Sigma^0\_m$ formula $\backslash phi(s)$ such that each number ''n'' is in ''A'' if and only if $\backslash phi(n)$ holds. It is known that if a set is $\backslash Sigma^0\_m$ then it is $\backslash Sigma^0\_n$ for any $n\; >\; m$, but for each ''m'' there is a $\backslash Sigma^0\_$ set that is not $\backslash Sigma^0\_m$. Thus the number of quantifier alternations required to define a set gives a measure of the complexity of the set. Post's theorem uses the relativized arithmetical hierarchy as well as the unrelativized hierarchy just defined. A set ''A'' of natural numbers is said to be $\backslash Sigma^0\_m$ relative to a set ''B'', written $\backslash Sigma^\_m$, if ''A'' is definable by a $\backslash Sigma^0\_m$ formula in an extended language that includes a predicate for membership in ''B''. While the arithmetical hierarchy measures definability of sets of natural numbers, Turing degrees measure the level of uncomputability of sets of natural numbers. A set ''A'' is said to be Turing reducible to a set ''B'', written $A\; \backslash leq\_T\; B$, if there is an oracle Turing machine that, given an oracle for ''B'', computes the characteristic function of ''A''. The Turing jump of a set ''A'' is a form of the Halting problem relative to ''A''. Given a set ''A'', the Turing jump $A\text{'}$ is the set of indices of oracle Turing machines that halt on input ''0'' when run with oracle ''A''. It is known that every set ''A'' is Turing reducible to its Turing jump, but the Turing jump of a set is never Turing reducible to the original set. Post's theorem uses finitely iterated Turing jumps. For any set ''A'' of natural numbers, the notation $A^$ indicates the ''n''-fold iterated Turing jump of ''A''. Thus $A^$ is just ''A'', and $A^$ is the Turing jump of $A^$. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Post's theorem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.